/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package topcoder;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author azouz
 */
public class SmartWordToy {

    public int minPresses(String start, String finish, String[] forbid) {
        HashMap<String, Boolean> visitedWords = new HashMap<String, Boolean>();
        Queue<String> q = new LinkedList<String>();
        int state = 0;
        q.add(start);
        while (!q.isEmpty()) {
            String newStart = q.remove();
            state++;
            for (int i = 0; i < newStart.length(); i++) {
                char next = (char) ((int) newStart.charAt(i) + 1);
                if ((int) newStart.charAt(i) == 'z') {
                    next = 'a';
                }

                StringBuilder ss = new StringBuilder(newStart);
                ss.setCharAt(i, next);
                String word = ss.toString();
                if (word.equals(finish)) {
                    return state;
                }
                if (!visitedWords.containsKey(word)) {
                    visitedWords.put(word, true);
                    if (!this.isforbid(word, forbid)) {
                        q.add(word);
                    }
                }
                char prev = (char) ((int) newStart.charAt(i) - 1);
                if ((int) newStart.charAt(i) == 'a') {
                    prev = 'z';
                }
                ss = new StringBuilder(newStart);
                ss.setCharAt(i, prev);
                word = ss.toString();
                if (word.equals(finish)) {
                    return state;
                }
                if (!visitedWords.containsKey(word)) {
                    visitedWords.put(word, true);
                    if (!this.isforbid(word, forbid)) {
                        q.add(word);
                    }
                }

            }
        }
        return -1;
    }

    private boolean isforbid(String s, String[] forbid) {
        System.out.println("Word = " + s);
        for (int i = 0; i < forbid.length; i++) {
            String[] forbidWord = forbid[i].split(" ");
            for (int j = 0; j < forbidWord.length; j++) {
                if (forbidWord[j].equals(s.charAt(j) + "")) {
                    return true;
                }
            }
        }
        return false;
    }

    private int genrateSecond(String s, Queue<String> q, HashMap<String, Boolean> visitedWords, int state, String finish) {
        boolean flg = false;
        for (int i = 0; i < s.length(); i++) {
            if ((int) s.charAt(i) - 1 >= (int) 'a') {
                char prev = (char) ((int) s.charAt(i) - 1);
                StringBuilder ss = new StringBuilder(s);
                ss.setCharAt(i, prev);
                if (visitedWords.containsKey(ss.toString()) && !visitedWords.get(ss.toString())) {
                    visitedWords.put(ss.toString(), true);
                    q.add(ss.toString());
                    flg = true;
                }
            }
            if ((int) s.charAt(i) + 1 <= (int) 'z') {
                char next = (char) ((int) s.charAt(i) + 1);
                StringBuilder ss = new StringBuilder(s);
                ss.setCharAt(i, next);
                if (visitedWords.containsKey(ss.toString()) && !visitedWords.get(ss.toString())) {
                    visitedWords.put(ss.toString(), true);
                    q.add(ss.toString());
                    flg = true;
                }
            }
        }
        if (flg) {
            state++;
        }
        return state;
    }

    public static void main(String[] args) {
        SmartWordToy s = new SmartWordToy();
        String forbid[] = {"a a a z", "a a z a", "a z a a", "z a a a", "a z z z", "z a z z", "z z a z", "z z z a"};
        String start = "aaaa";
        String finish = "zzzz";
        System.out.println(s.minPresses(start, finish, forbid));

    }
}